export async function* heapSort(array, compare, swap, set) {
    const n = array.length;
    
    // Build max heap
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        yield* heapify(array, n, i, compare, swap);
    }
    
    // Extract elements from heap one by one
    for (let i = n - 1; i > 0; i--) {
        yield { type: 'swap', indices: [0, i] };
        await swap(0, i);
        
        yield { type: 'set', index: i, value: array[i] };
        
        yield* heapify(array, i, 0, compare, swap);
    }
    
    yield { type: 'set', index: 0, value: array[0] };
    yield { type: 'complete' };
}

async function* heapify(array, n, i, compare, swap) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    
    if (left < n) {
        yield { type: 'compare', indices: [largest, left] };
        if (await compare(largest, left)) {
            largest = left;
        }
    }
    
    if (right < n) {
        yield { type: 'compare', indices: [largest, right] };
        if (await compare(largest, right)) {
            largest = right;
        }
    }
    
    if (largest !== i) {
        yield { type: 'swap', indices: [i, largest] };
        await swap(i, largest);
        
        yield* heapify(array, n, largest, compare, swap);
    }
}